package Year22_Month06.day25;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class 组合总和3 {
    List<List<Integer>> list = new ArrayList<>();
    LinkedList<Integer> mylist = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracting(n,k,0,1);
        return list;
    }

    public void backtracting(int n,int k,int sum,int startIndex){
        if(sum == n && mylist.size() == k){
            //如果说当前数字的总和等于n并且长度是k，就返回
            list.add(new ArrayList<>(mylist));
            return;
        }
        //在这里进行剪枝
        //if(sum > n || mylist.size() > k) return;
        for(int i = startIndex;i <= 9 - (k-mylist.size()) + 1;i++){
            mylist.add(i);
            if(sum + i <= n) {
                backtracting(n, k, sum + i, i + 1);
            }
            mylist.removeLast();
        }
    }
}
